class Solution {
public:
    int maxProfit(int k, vector<int>& prices)
    {
        int n = prices.size();
        vector dp(n, vector(2, vector<int>(k + 1)));
        for (int j = 1; j <= k; j++)
        {
            dp[0][0][j] = -prices[0];
            dp[0][1][j] = 0;
        }
        for (int i = 1; i < n; i++)
        {
            for (int j = 1; j <= k; j++)
            {
                dp[i][0][j] = max(dp[i - 1][1][j - 1] - prices[i], dp[i - 1][0][j]);
                dp[i][1][j] = max(dp[i - 1][1][j], dp[i - 1][0][j] + prices[i]);
            }
        }
        return *max_element(dp[n - 1][1].begin(), dp[n - 1][1].end());
    }
};